package com.bichengcao.googlecodejam.practiceproblems;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.HashMap;

public class EggDrop {

	static int N;
	static final long LIMIT = 1L << 32;

	public static void main(String[] args) throws IOException {
		Input[] inputs = parseInput("src/com/bichengcao/googlecodejam/practiceproblems/C-large-practice.in");
		Output[] outputs = process(inputs);
		writeOutput("src/com/bichengcao/googlecodejam/practiceproblems/EggDrop.out", outputs);
	}

	static class Input {

		int F;
		int D;
		int B;
	}

	static class Output {

		long F;
		int D;
		int B;
	}

	private static Input[] parseInput(String filename) throws IOException {
		BufferedReader in = new BufferedReader(new FileReader(filename));
		N = Integer.parseInt(in.readLine());
		Input[] array = new Input[N];

		for (int i = 0; i < N; i++) {
			Input input = array[i] = new Input();
			String line = in.readLine();
			String[] splits = line.split(" ");
			input.F = Integer.parseInt(splits[0]);
			input.D = Integer.parseInt(splits[1]);
			input.B = Integer.parseInt(splits[2]);
		}

		in.close();
		return array;
	}

	static HashMap<Integer, HashMap<Integer, Long>> cache = new HashMap<Integer, HashMap<Integer, Long>>();

	// Cache the minimum D for each B from 2 to 32 to get F exceeds limit
	static int[] db = new int[33];
	
	private static Output[] process(Input[] inputs) {
		for (int i = 2; i <= 32; i++) {
			int j = 1;
			while (solve(j, i) != -1) {
				j++;
			}
			db[i] = j;
		}
		
		Output[] outputs = new Output[N];
		for (int i = 0; i < N; i++) {
			outputs[i] = process(inputs[i]);
		}
		return outputs;
	}

	private static Output process(Input input) {
		Output output = new Output();
		
		// if B > D, then we can just reduce B to D and it will not impact result
		if (input.B > input.D) {
			input.B = input.D;
		}

		if (input.B > 32 || (input.B >= 2 && input.D >= db[input.B])) {
			output.F = -1;
		} else {
			output.F = solve(input.D, input.B);
		}
		
		if (input.B > 32) {
			output.D = findD(1, input.B, input);
		} else if (input.B == 1) {
			output.D = input.F;
		} else {
			output.D = findD(1, Math.min(db[input.B], input.D), input);
		}
		
		if (input.D >= input.F) {
			output.B = 1;
		} else {
			for (int i = 2; i <= input.B; i++) {
				if (solve(Math.min(db[i], input.D), i) == -1 
						|| solve(Math.min(db[i], input.D), i) >= input.F) {
					output.B = i;
					break;
				}
			}
		}

		return output;
	}

	/**
	 * Use binary search to find D minimum.
	 */
	private static int findD(int lower, int upper, Input input) {
		if (lower == upper) return lower;
		int mid = (lower + upper) / 2;
		if (solve(mid, input.B) == -1 || solve(mid, input.B) >= input.F) {
			return findD(lower, mid, input);
		} else {
			return findD(mid + 1, upper, input);
		}
	}

	/**
	 * Calculate maximum F given D and B and return -1 if maximum F exceeds 2 ^ 32.
	 */
	private static long solve(int d, int b) {
		if (d <= b) {
			if (d > 32) {
				return -1;
			}
			return (1L << d) - 1;
		}
		if (b == 1) {
			return d;
		}
		HashMap<Integer, Long> bmap = cache.get(d);
		if (bmap == null) {
			bmap = new HashMap<Integer, Long>();
			cache.put(d, bmap);
		}
		if (bmap.get(b) != null) {
			return bmap.get(b);
		}
		
		long result;
		if (solve(d - 1, b) == -1) {
			result = -1;
		} else {
			/*
			 * F(d, b) can be calculated by trying one egg at floor X = F(d-1, b-1) + 1, if it breaks,
			 * all floors below X can be determined since the height is F(d-1, b-1). Otherwise,
			 * there are F(d-1, b) floors can be determined above X given the egg quota left.
			 */
			result = solve(d - 1, b - 1) + solve(d - 1, b) + 1;
			if (result >= LIMIT) {
				result = -1;
			}
		}
		
		bmap.put(b, result);
		
		return result;
	}

	private static void writeOutput(String filename, Output[] outputs) throws IOException {
		PrintWriter out = new PrintWriter(new FileWriter(filename));
		for (int i = 0; i < N; i++) {
			out.println("Case #" + (i + 1) + ": " + outputs[i].F + " " + outputs[i].D + " "
					+ outputs[i].B);
		}
		out.close();
	}

}
